第六章 树和二叉树                                                             

一、下面是有关二叉树的叙述，请判断正误

（   ）1. 二叉树中每个结点的两棵子树的高度差等于1。 
（   ）2. 二叉树中每个结点的两棵子树是有序的。    
（   ）3. 二叉树中所有结点个数是2k-1-1，其中k是树的深度。 
（   ）4. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 
（   ）5. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i－1个结点。
（   ）6. 具有12个结点的完全二叉树有5个度为2的结点。

二、填空

1. 由３个结点所构成的二叉树有      种形态。
2. 一棵深度为6的满二叉树有              个分支结点和            个叶子。
3. 一棵具有２５７个结点的完全二叉树，它的深度为        。

4. 设一棵完全二叉树有700个结点，则共有        个叶子结点。

5. 一棵含有n个结点的k叉树，可能达到的最大深度为      ，最小深度为          。

三、选择题

（    ）1． 不含任何结点的空树         。
          （Ａ）是一棵树           （Ｂ）是一棵二叉树           （Ｃ）是一棵树也是一棵二叉树           （Ｄ）既不是树也不是二叉树

（    ）2．二叉树是非线性数据结构，所以             。
          （Ａ）它不能用顺序存储结构存储           （Ｂ）它不能用链式存储结构存储          
          （Ｃ）顺序存储结构和链式存储结构都能存储           （Ｄ）顺序存储结构和链式存储结构都不能使用

（    ）3.  具有n(n>0)个结点的完全二叉树的深度为         。
          （Ａ）élog2(n)ù           （B）ë log2(n)û            （C） ë log2(n) û+1            （D）élog2(n)+1ù

（    ）4．把一棵树转换为二叉树后，这棵二叉树的形态是           。
          （Ａ）唯一的           （Ｂ）有多种           （Ｃ）有多种，但根结点都没有左孩子           （Ｄ）有多种，但根结点都没有右孩子

          5. 二叉树  A   。在完全的二叉树中，若一个结点没有  B   ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的  C   ，而N的右子女是它在原树里对应结点的  D    。
           供选择的答案 ：
          A： ①是特殊的树      ②不是树的特殊形式      ③是两棵树的总称      ④有是只有二个根结点的树形结构
          B： ①左子结点      ② 右子结点      ③ 左子结点或者没有右子结点      ④ 兄弟
          C～D： ①最左子结点      ② 最右子结点      ③ 最邻近的右兄弟      ④ 最邻近的左兄弟      ⑤ 最左的兄弟      ⑥ 最右的兄弟
          答案：A=           B=         C=          D＝          

四、简答题

1. 一棵度为2的树与一棵二叉树有何区别？

2. 给定如图所示二叉树T，先序，中序，后序结果并请画出与其对应的中序线索二

五、阅读分析题

1.  把如图所示的树转化成二叉树。

2.【严题集6.21②】画出和下列二叉树相应的森林。